package  
{	
	/**
	 * When creating the ASTAR make sure to pass a vector of nodes cotaining the coordinate and the positions on stage and the columns
	 * of the grid.
	 * @author Lorenzo Nuvoletta
	 */
	public class AStar
	{
		private var _vNodeList		:Vector.<Node>;		
		private var _vPathList		:Vector.<int>;
		private var _vFinalPathList	:Vector.<int>;
		private var _startNode		:int;
		private var _endNode		:int;
		private var _columns		:int;
		private var _distances		:Vector.<Distance>;		
		private var _lastNode		:int;
		private var _progressive	:Boolean;
		private var _includeDiagonal:Boolean;
		private var _shortDistance	:Distance;
		private var _shrotDistFound :Boolean;		
		
		private var node			:Node;
		private var distance		:Distance;
		
		
		public function get startNode():int { return _startNode; }
		public function get endNode():int { return _endNode; }
		
		public function AStar(vNodeList:Vector.<Node>, columns:int) 
		{
			_vNodeList		= vNodeList;
			_lastNode		= vNodeList.length - 1;
			_columns		= columns;			
		}
		
		public function checkPath(startNode:int, endNode:int, progressive:Boolean = false, includeDiagonal:Boolean = false):Vector.<int> {
			reset(_vNodeList);
			_distances 		= new Vector.<Distance>();
			_progressive 	= progressive;
			_includeDiagonal = includeDiagonal;
			_vPathList		= new Vector.<int>();
			_vFinalPathList	= new Vector.<int>();
			_vPathList.push(_startNode = startNode);			
			_endNode = changeOffsetTile(endNode);
			_shortDistance = new Distance(calculateDistance(_startNode), _startNode);
			if (_startNode != _endNode) astar(_startNode);
			return _vFinalPathList;
		}
		
		private function changeOffsetTile(n:int):int 	{
			while (_vNodeList[n].closed && n!=_startNode) {
				n < _startNode ? n++ : n--;				
			}
			return n;
		}
		
		private function astar(n:int):void {			
			while (n != _endNode) {
				_vNodeList[n].visited = true;
				_shrotDistFound = false;
				var n1:Boolean = checkNode(n, n - 1);
				var n2:Boolean = checkNode(n, n + 1);
				var n3:Boolean = checkNode(n, n - _columns);
				var n4:Boolean = checkNode(n, n + _columns);
				if (_includeDiagonal) {
					if (n1 && n3) checkNode(n, n - _columns - 1);
					if (n1 && n4) checkNode(n, n + _columns - 1);
					if (n2 && n3) checkNode(n, n - _columns + 1);
					if (n2 && n4) checkNode(n, n + _columns + 1);						
				}				
				
				if (_shrotDistFound) {
					n = _shortDistance.nodeId;
					_vPathList.push(n);
				}
				else if (_distances.length > 0) {					
					distance = _distances.shift();					
					n = distance.nodeId;					
					_vPathList.push(n);
				}
				else if ( _progressive){					
					_endNode = n = _shortDistance.nodeId;
					break;					
				}
				else {					
					trace('Path not found');					
					return;
				}				
			}
					
			node = _vNodeList[_endNode];
			_vFinalPathList.push(_endNode);
			for (var i:int = _vPathList.length - 1; i >= 0; i--) {				
				if (node.parent == _vPathList[i]) {
					_vFinalPathList.push(node.parent); 
					node = _vNodeList[node.parent];
				}
				if (node.parent == _startNode) {
					_vFinalPathList.push(_startNode);
					return;
				}
			}
			//_vFinalPathList = _vPathList;
		}
		
		private function checkNode(n:int, numNode:int):Boolean {			
			if ( ( n != numNode + 1 || (numNode + 1) % _columns ) && ( n != numNode - 1 || (numNode) % _columns ) ) {
				if (numNode < 0 || numNode>_lastNode) return false;
				else node = _vNodeList[numNode];
				
				if (node && !node.closed && !node.visited) {
					_vNodeList[numNode].parent = n;					
					
					var dist:Distance = new Distance( calculateDistance(numNode), numNode);
					if (_shortDistance.distance > dist.distance) {
						_shortDistance = dist;
						_shrotDistFound = true;
					}
					
					var length:int = _distances.length;
					for (var i:int = 0; i < length; i = (i << 1) + 1) {			
						if (_distances[i].distance > dist.distance) break; 
					}					
					i && i < length ? _distances.splice(i, 0, dist) : !i ? _distances.unshift(dist) : _distances.push(dist);
					
					_vNodeList[numNode].visited = true;
					return true;
				}
				else return false;
			}
			else return false;
		}		
		
		// reset the visited parameter in nodeList
		private function reset(nodeList:Vector.<Node>):void {			
			for each(var n:Node in nodeList) {
				n.visited = false;
			}			
		}
		
		//Calculate distance between n and endNode
		private function calculateDistance(n:int):int {
			var x:int = _vNodeList[_endNode].x - _vNodeList[n].x;
			var y:int = _vNodeList[_endNode].y - _vNodeList[n].y;
			return abs(x) + abs(y);
		}
		
		//Abs function
		private function abs(x:int):int {
			return (x ^ (x >> 31)) - (x >> 31);
		}
		
	}

}